package 学习计划.数据结构;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _238_除自身以外数组的乘积 {
    /**
     * 耍赖做法  不符合题意
     * 执行用时：1ms，内存消耗：49.8MB
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        int sum = 1;
        int count = 0;
        for (int num : nums) {
            if (num != 0) {
                sum *= num;
            } else {
                count++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (count != 1) {
                    ret[i] = 0;
                } else {
                    ret[i] = sum;
                }
            } else {
                if (count > 0) {
                    ret[i] = 0;
                } else {
                    ret[i] = sum / nums[i];
                }
            }
        }
        return ret;
    }


    /**
     * 使用额外数组来存储左右两端的乘积
     * 执行用时：1ms，内存消耗：49.7MB
     * @param nums
     * @return
     */
    public int[] productExceptSelf2(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return nums;
        }
        int[] ret = new int[n];

        // init L和R 数组
        int[] L = new int[n];
        int[] R = new int[n];
        L[0] = 1;
        R[n - 1] = 1;
        for (int i = 1; i < n; i++) {
            L[i] = L[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            R[i] = R[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            ret[i] = L[i] * R[i];
        }
        return ret;
    }

    /**
     * 将ret数组当做L数组，R数组在遍历中采用int数字的形式来算
     * 执行时间：1ms，内存消耗：49.5MB
     * @param nums
     * @return
     */
    public int[] productExceptSelf3(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return nums;
        }
        int[] ret = new int[n];
        ret[0] = 1;
        for (int i = 1; i < n; i++) {
            ret[i] = ret[i - 1] * nums[i - 1];
        }

        int R = 1;
        for (int i = n - 1; i >= 0; i--) {
            ret[i] = ret[i] * R;
            R *= nums[i];
        }
        return ret;
    }
}
